package com.liunian.algorithmstudy.dynamic.completebackpack;

import java.util.Arrays;

public class NumSquares279 {

	/**
	 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
	 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。
	 例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

	 示例 1：
	 输入：n = 12
	 输出：3
	 解释：12 = 4 + 4 + 4

	 示例 2：
	 输入：n = 13
	 输出：2
	 解释：13 = 4 + 9
	 */

	public int numSquares(int n) {
		int[] dp = new int[n + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		for (int i = 0; i <= (int) Math.sqrt(n); i++) {
			for (int j = i * i; j <= n; j++) {
				if (dp[j - i * i] != Integer.MAX_VALUE) {
					dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
				}
			}
		}
		return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
	}

	public static void main(String[] args) {
		NumSquares279 num = new NumSquares279();
		System.out.println(num.numSquares(11));
	}

}
